package com.LeeCode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * 几乎唯一子数组的最大和
 */

public class Code2841 {
    public static void main(String[] args) {
        int[] arr = {2, 6, 7, 3, 1, 7};
        int k = 4, m = 3;

        List<Integer> nums = new ArrayList<>();
        for (int num : arr) {
            nums.add(num);
        }

        System.out.println(new Code2841().maxSum(nums, m, k));
    }

    public long maxSum(List<Integer> nums, int m, int k) {
        long ans = 0, curSum = 0;
        HashMap<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < nums.size(); i++) {
            curSum += nums.get(i);
            map.put(nums.get(i), map.getOrDefault(nums.get(i), 0) + 1);

            if (i < k - 1) {
                continue;
            }

            if (map.size() >= m && curSum > ans)
                ans = curSum;

            curSum -= nums.get(i - k + 1);
            map.put(nums.get(i - k + 1), map.get(nums.get(i - k + 1)) - 1);
            if (map.get(nums.get(i - k + 1)) == 0)
                map.remove(nums.get(i - k + 1));
        }
        return ans;
    }
}
